package sysu.el.graph.undi.algor;

import sysu.el.array.TagArray;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.graph.undi.UndiGTAdjList;

public class SearchDividedBranches {
	public TagArray tag = null;

	public UndiGTAdjList adjList = null;
	public ArrQueueInt queue = null;
	public SearchDividedBranches(UndiGTAdjList adjList){
		this.adjList = adjList;
		tag = new TagArray(adjList.getNodeNum());
		queue = new ArrQueueInt(adjList.getNodeNum());
	}

	private int curTag;
	public void addQueue(int newNode){
		if (tag.isNotTag(newNode)){
			this.queue.add(newNode);
			tag.setTag(newNode, curTag);
		}
	}

	public void search(UndiGTAdjList adjList, int root){
		assert(adjList.getNodeNum() <= this.tag.size());
		this.adjList = adjList;

		// zero is for root;
		int tagNum = adjList.getDegree(root) + 1;
		tag.reset(tagNum);
		
		this.curTag = 0;
		tag.setTag(root, curTag);

		for (curTag = tagNum-1 ; curTag>0; --curTag){
			queue.reset();
			this.addQueue(this.adjList.getList(root)[curTag-1]);
			
			while (queue.isNotEmpty()){
				int h = queue.forward();
				int list [] = this.adjList.getList(h);
				int counter = this.adjList.getDegree(h) -1;
				while (counter >= 0){
					int next = list[counter];
					this.addQueue(next);
					counter --;
				} // End While
			} // End while
		}

	}
}

